Coevolution

上禮拜在 group meeting 稍微介紹了一下在 Utrecht 做的畢業論文研究，主題是 "a comparison of evaluation methods in co-evolution"，屬於 Evolutionary Computation (or genetic algorithm) 的領域。Coevolution 在 ACM SIGEVO 裡現在也變成一個獨立的主題，我想寫一篇簡單的「無痛入門」，並且介紹一下一些有趣的延伸觀察。


Coevolution 本來是演化論裡面描述關於一個以上的物種交互影響而共同演化的過程，在計算經濟學(computational economics)以及賽局理論(game theory) 興起之後，逐漸形成一種研究個體之間策略演變的理論模型；而在 evolutionary computation 的領域裡，也發展成一種「難以定義目標」的情況下的搜尋方法。

由於我做的主題屬於 evolutionary computation，所以就先簡單的介紹一下這個領域的背景知識。我們利用電腦來做計算，search problems 算是最常見的應用之一：在眾多可能的答案(so-called search space)之中，找到符合我們給定的條件的解答。然而有時候由於答案的可能性太多(所以沒辦法每個可能性都檢查到)、條件太過複雜(所以很難找到「最好」的解答)....等因素，傳統的搜尋方法效率不彰，因此就有人仿照生物演化的理論模型，設計出一種叫做 genetic algorithm 的搜尋方法，在很多情況下可以更迅速的找到更好的解答。

這種 genetic algorithm (中文好像是譯做 [遺傳演算法] 的樣子) 的運作，需要使用者根據他要搜尋的需求 (比方說，搜尋一組中獎機率最高的六個號碼)，設計一個 [適性函數] (fitness function) 來判斷每個解答(在這個例子裡就是每種六個號碼的組合) 的好壞 (在這個例子裡可能是要指定這組數字的中獎機率)，然後根據這個函數給定的好壞程度，來決定要保留哪些解答，以及繼續搜尋新解答的方向。

然而，在很多情況下，我們並不知道這個 [適應程度] 該怎麼定義。比方說下棋策略的好壞，是要跟其他策略比較之下才知道的，而無法單從一個策略本身的各種性質中得知；又比方說要給定一組六個數字中獎的機率，雖然可以從過去的中獎機率來作預測，但是究竟要怎樣推算才正確其實誰也說不準。
這時，coevolution 給了我們一種新的可能性：用另一組 genetic algorithm 來決定適性函數。如此一來，適性函數由固定的評估方式，轉變成動態的評估過程，而原本難以定義的評估方式也可以由「互動」來取代。

講了半天還是很抽象，不如舉個實際的例子：老師跟學生。教育的目的是想培育學生成為國家未來的棟樑，但是這個目標很抽象，在現實上也很難定義一套固定的評分標準來評估一個學生未來是不是能夠 [成為國家未來的棟樑]，因此，教育就很不適合用「朝向某個特定目標作最佳化」的方式來執行。（可惜的是，我們一直都在這麼辦教育....）

那麼，怎麼做 coevolution，才能在目標不是很明確的情況下，還是隱隱的向那個抽象的理想邁進？傳統的作法是考慮 performance，或是某種評量下的分數，在「老師跟學生」這個比喻之中，就是學生考試成績越高越好、老師出題越難越好。然而這幾年有人提出 "informativeness" 的概念，指出只考慮 performance 的做法事實上很容易讓整個 evolutionary search 偏向某個方向，因此還要考慮是否能在另外一個群體裡表現出多樣性的能力，以前面的例子來說就是：老師出的題目是不是可以讓很多學生的得分都不同；而學生是不是能夠讓每個老師的題目有不同的難度。

實驗的結果，是加上 informativeness 之後，coevolution 變得很有效率，但是就其隱身的涵義來說，其實這是教育學或生態學早就有的結論：多元化與多樣性。簡單的說，我們的研究在某種意義上，用複雜的數學模型來詮釋了多元化與多樣性的好處。


以上。不過我想這樣寫大部分人應該還是看不懂，反正就先當初搞，以後再改吧。